{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The kth Factor of n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthFactor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #n 的第 k 个因子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数&nbsp;<code>n</code> 和&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果正整数 <code>i</code> 满足 <code>n % i == 0</code> ，那么我们就说正整数 <code>i</code> 是整数 <code>n</code>&nbsp;的因子。</p>\n",
    "\n",
    "<p>考虑整数 <code>n</code>&nbsp;的所有因子，将它们 <strong>升序排列</strong>&nbsp;。请你返回第 <code>k</code>&nbsp;个因子。如果 <code>n</code>&nbsp;的因子数少于 <code>k</code>&nbsp;，请你返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 12, k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>因子列表包括 [1, 2, 3, 4, 6, 12]，第 3 个因子是 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, k = 2\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>因子列表包括 [1, 7] ，第 2 个因子是 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, k = 4\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>因子列表包括 [1, 2, 4] ，只有 3 个因子，所以我们应该返回 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= n &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<p>你可以设计时间复杂度小于 O(n) 的算法来解决此问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-kth-factor-of-n](https://leetcode.cn/problems/the-kth-factor-of-n/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-kth-factor-of-n](https://leetcode.cn/problems/the-kth-factor-of-n/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['12\\n3', '7\\n2', '4\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        f1 = []\n",
    "        f2 = []\n",
    "        for num in range(1, int(sqrt(n))+1):\n",
    "            if n % num  == 0:\n",
    "                f1.append(num)\n",
    "                f2.append(n//num)\n",
    "        if f1[-1] == f2[-1]:\n",
    "            f1.pop()\n",
    "        f = f1 + f2[::-1]\n",
    "        return f[k-1] if len(f) >= k else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        arr = []\n",
    "        for i in range (1,n+1):\n",
    "            if n%i == 0:\n",
    "                arr.append(i)\n",
    "        if len(arr) < k:\n",
    "            return -1\n",
    "        else:\n",
    "            return arr[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "\n",
    "        ans = set()\n",
    "        \n",
    "        for i in range(1, int(math.sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                ans.add(i)\n",
    "                ans.add(n // i)\n",
    "            \n",
    "        if len(ans) < k:\n",
    "            return -1\n",
    "        return sorted(list(ans))[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        cnt=0\n",
    "        for i in range(1,n+1):\n",
    "            if n%i==0:\n",
    "                cnt+=1\n",
    "            if cnt==k:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "        思路：\n",
    "        方法一：枚举\n",
    "        我们可以从小到大枚举所有在 [1,n] 范围内的数，并判断是否为 n 的因子。\n",
    "        \"\"\"\n",
    "        count = 0\n",
    "        for factor in range(1, n+1):  # n+1\n",
    "            if n % factor == 0:\n",
    "                count += 1\n",
    "                if count == k:\n",
    "                    return factor\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        for i in range(1,n+1):\n",
    "            if n % i == 0:\n",
    "                k -= 1 \n",
    "            if k == 0:\n",
    "                return i \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        res = [x for i in range(1, isqrt(n)+1) for x in {i,n//i} if n%i==0]\n",
    "        return sorted(res)[k-1] if len(res)>=k else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        weilan=int(sqrt(n+1e-7))\n",
    "        ans=[]\n",
    "        for i in range(1,weilan+1):\n",
    "            if n%i==0:\n",
    "                ans.append(int(i))\n",
    "\n",
    "                if n/i!=i:\n",
    "                    ans.append(int(n/i))\n",
    "        ans.sort()\n",
    "        return ans[k-1] if k<=len(ans) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        for p in range(1, n+1):\n",
    "            if n % p == 0:\n",
    "                k -= 1\n",
    "\n",
    "            if k == 0:\n",
    "                return p\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        factors=[]\n",
    "        if n==1:\n",
    "            factors=[1]\n",
    "        else:\n",
    "            lasthalf=[]\n",
    "            firsthalf=[]\n",
    "            stop=False\n",
    "            for i in range(1,n+1):                \n",
    "                if i not in lasthalf:\n",
    "                    print(n//i,lasthalf)\n",
    "                    if n%i==0:\n",
    "                        firsthalf.append(i)\n",
    "                        if n%i==n//i:\n",
    "                            lasthalf.append(n//i)\n",
    "                else:\n",
    "                    break\n",
    "            lasthalf.reverse()\n",
    "            factors=firsthalf+lasthalf\n",
    "        if k>len(factors):\n",
    "            return -1\n",
    "        \n",
    "        return factors[k-1] \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        for i in range(1,n+1):\n",
    "            if n % i == 0:\n",
    "                k -= 1\n",
    "                if k == 0:\n",
    "                    return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        cout=[]\n",
    "        for i in range(1,n+1):\n",
    "            if n%i==0:\n",
    "                cout.append(i)\n",
    "        if k>len(cout):\n",
    "            return -1\n",
    "        else:\n",
    "            return cout[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthFactor(self, n: int, k: int) -> int:\n",
    "        count = 0\n",
    "        factor = 1\n",
    "        while factor * factor <= n:\n",
    "            if n % factor == 0:\n",
    "                count += 1\n",
    "                if count == k:\n",
    "                    return factor\n",
    "            factor += 1\n",
    "        factor -= 1\n",
    "        if factor * factor == n:\n",
    "            factor -= 1\n",
    "        while factor > 0:\n",
    "            if n % factor == 0:\n",
    "                count += 1\n",
    "                if count == k:\n",
    "                    return n // factor\n",
    "            factor -= 1\n",
    "        return -1\n",
    "\n",
    "        '''\n",
    "        nSet = set()\n",
    "        right = n\n",
    "        for left in range(1, n+1):\n",
    "            if left in nSet:\n",
    "                break\n",
    "            if n % left == 0:\n",
    "                nSet.add(left)\n",
    "                right = n // left\n",
    "                nSet.add(right)\n",
    "\n",
    "        nlist = sorted(nSet)\n",
    "        return nlist[k-1] if k-1 < len(nlist) else -1\n",
    "        '''\n",
    "\n",
    "        '''\n",
    "        count = 0\n",
    "        for factor in range(1, n+1):\n",
    "            if n % factor == 0:\n",
    "                count += 1\n",
    "                if count == k:\n",
    "                    return factor\n",
    "        return -1\n",
    "        '''"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
